import java.util.Arrays;
import java.util.Comparator;

public class MergeSort<T> {
    private Comparator<T> comparator;

    public MergeSort(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    public void sort(T[] array, int start, int end) {
        if (end - start <= 1) {
            return;
        }

        int mid = start + ((end - start) >> 1);
        sort(array, start, mid);
        sort(array, mid, end);
        merge(array, start, mid, end);
    }

    private void merge(T[] array, int start, int mid, int end) {
        T[] leftPart = Arrays.copyOfRange(array, start, mid);

        int left = 0;
        int right = mid;

        int i = start;
        while (left < leftPart.length && right < end) {
            if (comparator.compare(leftPart[left], array[right]) <= 0) {
                array[i++] = leftPart[left++];
            } else {
                array[i++] = array[right++];
            }
        }

        while (left < leftPart.length) {
            array[i++] = leftPart[left++];
        }

    }
}
